package 单周赛.history;

import java.util.*;

/**
 *
 */
public class 第352场单周赛 {

    public static void main(String[] args) {

        第352场单周赛 impl = new 第352场单周赛();
        System.out.println(impl.findPrimePairs(5));

        System.out.println(impl.continuousSubarrays(new int[]{5, 4, 2, 4}));

    }

    // 注意：静态变量和静态代码块的文件顺序就是加载顺序
    private static Set<Integer> primeSet = new HashSet<>();

    static {
        // 静态代码块的执行不会记录的执行时间里面
        collectPrime(1000001);
    }

    /**
     * 预处理埃氏筛得到 <= n 的所有质数+双指针
     */
    public List<List<Integer>> findPrimePairs(int n) {
        List<List<Integer>> lists = new ArrayList<>();

        int left = 2, right = n;
        while (left <= right) {
            while (left < right && left + right > n) {
                right--;
            }
            if (left + right == n && primeSet.contains(left) &&
                    primeSet.contains(right)) {
                List<Integer> list = new ArrayList<>();
                list.add(left);
                list.add(right);
                lists.add(list);
            }
            left++;
        }
        return lists;
    }

    private static void collectPrime(int n) {
        int[] record = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            if (record[i] == 0) {
                primeSet.add(i);
            }

            int j = i;
            while ((long) j * i <= n) {
                record[j * i] = 1;
                j++;
            }
        }
    }

    /**
     * 滑动窗口+平衡树
     * 枚举右端点 right , 如果平衡树的 最大值-最小值 > 2,
     * 则将左端点 nums[left] 在平衡树中统计的个数 -1
     */
    public long continuousSubarrays(int[] nums) {
        long cnt = 0;
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            treeMap.put(nums[right],
                    treeMap.getOrDefault(nums[right], 0) + 1);

            while (treeMap.lastKey() - treeMap.firstKey() > 2) {
                treeMap.put(nums[left], treeMap.get(nums[left]) - 1);
                if (treeMap.get(nums[left]) == 0) {
                    treeMap.remove(nums[left]);
                }
                left++;
            }

            cnt += right - left + 1;
        }
        return cnt;
    }
}
